package graph_base_expression.adjset;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * @author sijunqiang
 * @data 2021/6/12 14:01
 * @description: 邻接表
 * 底层-使用红黑树表示的邻接表
 */
public class AdjSet {


    // v- 表示图中顶点个数
    private int V;

    // E-- 表示图中的边的个数
    private int E;

    // 使用红黑树的方式存储元素
    private TreeSet<Integer>[] adj;


    // 建图
    public AdjSet(String filename) {
        // 先读取文件数据
        File file = new File(filename);

        // 一行一行读  使用这种方式的话 不用关闭流资源
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt(); // V -代表图中顶点的个数
            if (V < 0) {
                throw new IllegalArgumentException("读取的数据 顶点不合法");
            }
            adj = new TreeSet[V]; // 创建一个红黑树数组
            for (int i = 0; i < V; i++)
                adj[i] = new TreeSet<Integer>();// 每个节点都是一个红黑树

            E = scanner.nextInt(); // E -- 代表图中边的个数
            if (E < 0) {
                throw new IllegalArgumentException("E- " + E + "is illegal!");
            }

            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                if (a == b) {
                    throw new IllegalArgumentException("发现平行边");
                }
                if (adj[a].contains(b)) {// 因为是使用的是红黑树 那么它的时间复杂度为O(log^n)
                    throw new IllegalArgumentException("发现自环边");
                }

                // 添加顶点
                adj[a].add(b); //  在a的顶点上面添加b顶点
                adj[b].add(a); // 在b的顶点添加a顶点
            }
        } catch (IOException e) {
            e.fillInStackTrace();
        }
    }

    // 获取图中顶点的个数
    public int V() {
        return V;
    }

    // 获取图中边的个数
    public int E() {
        return E;
    }

    // 判断图中两个顶点是否相邻
    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }

    // 求一个顶点的相邻顶点
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }


    // 获取顶点的度
    public int degree(int v) {
        validateVertex(v);
        return adj[v].size();
    }


    // 校验图的顶点是否合法
    private void validateVertex(int v) {
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("v " + v + " is illegal!");
        }
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n", V, E));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d : ", v));
            for (int w : adj[v]) {
                sb.append(String.format("%d ", w));
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        AdjSet adjSet = new AdjSet("graph_depth_first_traversal.txt");
        System.out.println(adjSet);

    }
}
